'''
https://leetcode.cn/problems/island-perimeter/description/
'''
from typing import List


class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        visited = [[False] * n for _ in range(m)]
        def dfs(i, j):
            perimeter = 4
            visited[i][j] = True
            for tx, ty in directions:
                tx, ty = tx + i, ty + j
                if 0 <= tx < m and 0 <= ty < n and grid[tx][ty] == 1:
                    perimeter -= 1
                    if not visited[tx][ty]:
                        perimeter += dfs(tx, ty)
            return perimeter
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    return dfs(i, j)
        return 0

    def islandPerimeter2(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        def dfs(i, j):
            perimeter = 4
            grid[i][j] = 2
            for tx, ty in directions:
                tx, ty = tx + i, ty + j
                if 0 <= tx < m and 0 <= ty < n and grid[tx][ty] != 0:
                    perimeter -= 1
                    if grid[tx][ty] == 1:
                        perimeter += dfs(tx, ty)
            return perimeter
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    return dfs(i, j)
        return 0